package com.hubu.tree.btree;
import java.util.LinkedList;
import java.util.Queue;
public abstract class AbstractBTreeNode<K extends Comparable<K>> {
    protected final int degree;
    AbstractBTreeNode(int degree) {
        if (degree < 2) {
            throw new IllegalArgumentException("degree must >= 2");
        }
        this.degree = degree;
    }
     abstract boolean isLeaf();
    abstract K search(K key);
    abstract void insertNotFull(K key);
    abstract void deleteNotEmpty(K key);
    void insertKey(K key) {
        checkNotFull();
        int i = this.nkey();
        //move keys
        while (i > 0 && key.compareTo(this.getKey(i - 1)) < 0) {
            this.setKey(this.getKey(i - 1), i);
            i--;
        }
        this.setKey(key, i);
        this.setNKey(this.nkey() + 1);
    }
     abstract K getKey(int idx);
    protected K deleteKey(K key) {
        int index = indexOfKey(key);
        if (index >= 0) {
            return this.deleteKey(index);
        }
        return null;
    }
    protected K deleteKey(int index) {
        if (index < 0 || index >= this.nkey()) {
            throw new RuntimeException("Index is invalid.");
        }
        K result = this.getKey(index);
        while (index < this.nkey() - 1) {
            this.setKey(this.getKey(index + 1), index);
            index++;
        }
        this.setKey(null, this.nkey() - 1);
        this.setNKey(this.nkey() - 1);
        return result;
 
    }
     boolean existsKey(K key) {
        return indexOfKey(key) >= 0;
    }
    protected void replaceKey(K oldKey, K newKey) {
        int index = indexOfKey(oldKey);
        if (index >= 0) {
            setKey(newKey, index);
        }
    }
    protected abstract K setKey(K newKey, int oldKeyIndex);
    protected abstract void setChild(AbstractBTreeNode<K> sub, int index);
    protected void insertChild(AbstractBTreeNode<K> sub, int index) {
        int i = this.nchild();
        while (i > index) {
            this.setChild(this.getChild(i - 1), i);
            i--;
        }
        this.setChild(sub, index);
        this.setNChild(this.nchild() + 1);
    }
     abstract AbstractBTreeNode<K> getChild(int index);
    protected void deleteChild(AbstractBTreeNode<K> child) {
        int index = -1;
        for (int i = 0; i < nchild(); i++) {
            if (this.getChild(i) == child) {
                index = i;
                break;
            }
        }
        if (index >= 0) {
            deleteChild(index);
        }
    }
    protected AbstractBTreeNode<K> deleteChild(int index) {
        AbstractBTreeNode<K> result = null;
        if (index >= 0 && index < this.nchild()) {
            result = this.getChild(index);
            while (index < this.nchild() - 1) {
                this.setChild(this.getChild(index + 1), index);
                index++;
            }
            this.setChild(null, index);
            this.setNChild(this.nchild() - 1);
        }
        return result;
    }
    protected abstract void splitChild(int child);
    protected abstract K splitSelf(AbstractBTreeNode<K> newNode);
    protected abstract void merge(K middle, AbstractBTreeNode<K> sibling);
    protected abstract int setNKey(int nkey);
     abstract int nkey();
     abstract int nchild();
    protected abstract int setNChild(int nchild);
    protected int indexOfKey(K key) {
        for (int i = 0; i < this.nkey(); i++) {
            if (key.equals(this.getKey(i))) {
                return i;
            }
        }
        return -1;
    }
    protected boolean isFull() {
        return nkey() == degree * 2 - 1;
    }
    protected final void checkNotFull() {
        if (isFull()) {
            throw new RuntimeException(this.toString() + " is full.");
        }
    }
    static <K extends Comparable<K>> String BTreeToString(AbstractBTreeNode<K> root){
        StringBuffer sb = new StringBuffer();
        AbstractBTreeNode node;
        Queue<AbstractBTreeNode> queue = new LinkedList<>();
        queue.add(root);
        String newLine = System.getProperty("line.separator");
        while (!queue.isEmpty()){
            node = queue.poll();
            sb.append(node).append(newLine);
            int i = 0;
            while (node.getChild(i) != null){
                queue.offer(node.getChild(i));
                i++;
            }
        }
        return sb.toString();
    }
}